# 从前序与中序遍历序列构造二叉树: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

        
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        """
            这道题还是比较考验编程能力的，脑子可以正确画出 二叉树，但是把思维转换为程序，确不知道咋写~

            1. 遍历 前序列表，因为 根左右的顺序，每次都遍历出来一个根节点
            2. 通过 中序列表，判断出来该节点的左右子节点

            比较规则：
            当前节点的 右边第一个节点：
            1. 如果在 中序列表中当前节点的左边， 那么它就是当前节点的左子节点
            2. 如果在 中序列表中当前节点的右边， 那么就要分情况：
                （1）如果在根节点的右边，那它一定是根节点的右部分，也就是右节点
                （2）如果还在根节点的左边， 那么它就是左子树的某个节点的 右子节点，经过分析实践（是它左边第一个节点）
                这点是最难的，归纳当前两条规律，实际上，它都是当前节点的左边第一个节点的右子节点！

            有了这两点，通过跌带，遍历前序列表， 很容易一步步判断出每一个为 根的当前节点的左右子节点，从而完成二叉树的创建！

            根据上述规律， 使用迭代的方式，利用栈辅助, hashmap, 遍历时 i 和 i - 1的关系
        """
        stack = list()
        # 1. 创建根节点，根据前序
        root = TreeNode(preorder[0])
        stack.append(root)
        # 2. 为何提升查找效率，判断一个节点在另一个的左侧还是右侧， 提前构建 中序遍历的hash结构，数组索引为大小比较左右
        idxMap = dict()
        for i in range(len(inorder)): 
            idxMap[inorder[i]] = i
        # 3. 开始遍历 前序列表，创建二叉树
        for i in range(1, len(preorder)):
            pre = stack[-1]
            # 判断它是在上一节点的左侧还是右侧
            if idxMap.get(preorder[i]) < idxMap.get(preorder[i - 1]): # 在左
                pre.left = TreeNode(preorder[i])
                stack.append(pre.left)
            else: # 在右
                # 找到当前遍历节点中，左边离它最近的， 也就是当前栈中的节点，看它是哪个节点的右子节点
                while stack and idxMap.get(stack[-1].val) < idxMap.get(preorder[i]):
                    pre = stack.pop()
                pre.right = TreeNode(preorder[i])
                stack.append(pre.right)

        return root            
        

# 上面的方法使用的是 map 来确定在左还是在右，还可以优化，一个指针就能判断。


# 下面是递归的写法
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        """
            实际上可以是前序遍历的写法， 根据前序可以确定根节点， 根据中序可以确定 左右子树
            而左右子树，重复上述过程，就一步步的，递归出整个树了
        """
        def myBuildTree(preorder_left: int, preorder_right: int, inorder_left: int, inorder_right: int):
            if preorder_left > preorder_right:
                return None
            
            # 前序遍历中的第一个节点就是根节点
            preorder_root = preorder_left
            # 在中序遍历中定位根节点
            inorder_root = index[preorder[preorder_root]]
            
            # 先把根节点建立出来
            root = TreeNode(preorder[preorder_root])
            # 得到左子树中的节点数目
            size_left_subtree = inorder_root - inorder_left
            # 递归地构造左子树，并连接到根节点
            # 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
            root.left = myBuildTree(preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1)
            # 递归地构造右子树，并连接到根节点
            # 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
            root.right = myBuildTree(preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right)
            return root
        
        n = len(preorder)
        # 构造哈希映射，帮助我们快速定位根节点
        index = {element: i for i, element in enumerate(inorder)}
        return myBuildTree(0, n - 1, 0, n - 1)

